package pers.whj.sort.number;

import pers.whj.sort.SortException;

public class NumSort {
    public static final int MAX_SIZE = 500000000;

    private static void check(int[] data, int left, int right) throws SortException {
        if (data == null) {
            throw new SortException(SortException.EMPTY_DATA);
        }
        if (data.length > MAX_SIZE) {
            throw new SortException(SortException.LARGE_DATA);
        }
        if (left > right) {
            throw new SortException(SortException.CROSS_BORDER);
        }
    }

    private static void reverse(int[] data, boolean reverse, int left, int right) {
        if (reverse) {
            while (left < right) {
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        }
    }

    private static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    /**
     * 冒泡排序
     */
    public static void BubbleSort(int[] data, boolean reverse) throws SortException {
        BubbleSort(data, reverse, 0, data == null ? 0 : data.length - 1);
    }

    public static void BubbleSort(int[] data, boolean reverse, int left, int right) throws SortException {
        check(data, left, right);
        boolean flag;
        for (int i = left + 1; i <= right; i++) {
            flag = false;
            for (int j = right; j >= i; j--) {
                if (data[j - 1] > data[j]) {
                    int temp = data[j - 1];
                    data[j - 1] = data[j];
                    data[j] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
        reverse(data, reverse, left, right);
    }

    /**
     * 选择排序
     */
    public static void SelectionSort(int[] data, boolean reverse) throws SortException {
        SelectionSort(data, reverse, 0, data == null ? 0 : data.length - 1);
    }

    public static void SelectionSort(int[] data, boolean reverse, int left, int right) throws SortException {
        check(data, left, right);
        for (int i = left; i < right; i++) {
            int k = i;
            for (int j = i + 1; j <= right; j++) {
                if (data[k] > data[j]) {
                    k = j;
                }
            }
            if (k != i) {
                int temp = data[i];
                data[i] = data[k];
                data[k] = temp;
            }
        }
        reverse(data, reverse, left, right);
    }

    /**
     * 插入排序
     */
    public static void InsertSort(int[] data, boolean reverse) throws SortException {
        InsertSort(data, reverse, 0, data == null ? 0 : data.length - 1);
    }

    public static void InsertSort(int[] data, boolean reverse, int left, int right) throws SortException {
        check(data, left, right);
        for (int i = left + 1; i <= right; i++) {
            if (data[i - 1] > data[i]) {
                int temp = data[i];
                int j = i - 1;
                do {
                    data[j + 1] = data[j];
                    j--;
                } while (j >= left && data[j] > temp);
                data[j + 1] = temp;
            }
        }
        reverse(data, reverse, left, right);
    }

    /**
     * 希尔排序
     */
    public static void ShellSort(int[] data, boolean reverse) throws SortException {
        ShellSort(data, reverse, 0, data == null ? 0 : data.length - 1);
    }

    public static void ShellSort(int[] data, boolean reverse, int left, int right) throws SortException {
        check(data, left, right);
        int i, j, gap = right - left + 1;
        do {
            gap = gap / 3 + 1;
            for (i = left + gap; i <= right; i++) {
                if (data[i - gap] > data[i]) {
                    int temp = data[i];
                    j = i - gap;
                    do {
                        data[j + gap] = data[j];
                        j -= gap;
                    } while (j >= left && data[j] > temp);
                    data[j + gap] = temp;
                }
            }
        } while (gap > 1);
        reverse(data, reverse, left, right);
    }

    /**
     * 堆排序
     */
    public static void HeapSort(int[] data, boolean reverse) throws SortException {
        HeapSort(data, reverse, 0, data == null ? 0 : data.length - 1);
    }

    public static void HeapSort(int[] data, boolean reverse, int left, int right) throws SortException {
        check(data, left, right);
        for (int i = (right - left - 1) / 2; i >= 0; i--) {
            siftDown(data, i, right - left, left);
        }
        for (int i = right - left; i > 0; i--) {
            int temp = data[left];
            data[left] = data[left + i];
            data[left + i] = temp;
            siftDown(data, 0, i - 1, left);
        }
        reverse(data, reverse, left, right);
    }

    private static void siftDown(int[] data, int start, int end, int offset) {
        int i = start;
        int j = 2 * i + 1;
        int temp = data[i + offset];
        while (j <= end) {
            if (j < end && data[j + offset] < data[j + offset + 1]) {
                j++;
            }
            if (temp > data[j + offset]) {
                break;
            } else {
                data[i + offset] = data[j + offset];
                i = j;
                j = 2 * j + 1;
            }
        }
        data[i + offset] = temp;
    }

    /**
     * 归并排序
     */
    public static void MergeSort(int[] data, boolean reverse) throws SortException {
        MergeSort(data, reverse, 0, data == null ? 0 : data.length - 1);
    }

    public static void MergeSort(int[] data, boolean reverse, int left, int right) throws SortException {
        check(data, left, right);
        mergeSort(data, left, right);
        reverse(data, reverse, left, right);
    }

    private static void mergeSort(int[] data, int left, int right) {
        if (left < right) {
            int mid = (right + left) / 2;
            mergeSort(data, left, mid);
            mergeSort(data, mid + 1, right);
            merge(data, left, mid, right);
        }
    }

    private static void merge(int[] data, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        System.arraycopy(data, left, temp, 0, temp.length);
        int s1 = 0;
        int s2 = mid - left + 1;
        int t = left;
        while (s1 <= mid - left && s2 <= right - left) {
            if (temp[s1] > temp[s2]) {
                data[t++] = temp[s2++];
            } else {
                data[t++] = temp[s1++];
            }
        }
        while (s1 <= mid - left) {
            data[t++] = temp[s1++];
        }
        while (s2 <= right - left) {
            data[t++] = temp[s2++];
        }
    }

    /**
     * 快速排序
     */
    public static void QuickSort(int[] data, boolean reverse) throws SortException {
        QuickSort(data, reverse, 0, data == null ? 0 : data.length - 1);
    }

    public static void QuickSort(int[] data, boolean reverse, int left, int right) throws SortException {
        check(data, left, right);
        quickSort(data, left, right);
        reverse(data, reverse, left, right);
    }

    private static void quickSort(int[] data, int left, int right) {
        if (left < right) {
            int pivotPosition = partition(data, left, right);
            quickSort(data, left, pivotPosition - 1);
            quickSort(data, pivotPosition + 1, right);
        }
    }

    private static int partition(int[] data, int left, int right) {
        int pivot = data[left];
        while (left < right) {
            while (left < right && pivot <= data[right]) {
                right--;
            }
            data[left] = data[right];
            while (left < right && pivot >= data[left]) {
                left++;
            }
            data[right] = data[left];
        }
        data[left] = pivot;
        return left;
    }

    /**
     * 鸡尾酒排序
     * 基于冒泡，在向后交换最大数到尾部后，再向前交换最小数到头部
     */
    public static void CocktailSort(int[] data, boolean reverse) throws SortException {
        CocktailSort(data, reverse, 0, data == null ? 0 : data.length - 1);
    }

    public static void CocktailSort(int[] data, boolean reverse, int left, int right) throws SortException {
        check(data, left, right);
        boolean flag = true;
        int start = left;
        int end = right;
        while (flag) {
            flag = false;
            for (int i = start; i < end; i++) {
                if (data[i] > data[i + 1]) {
                    swap(data, i, i + 1);
                    flag = true;
                }
            }
            end--;
            for (int i = end; i > start; i--) {
                if (data[i] < data[i - 1]) {
                    swap(data, i, i - 1);
                    flag = true;
                }
            }
            start++;
        }
        reverse(data, reverse, left, right);
    }

    /**
     * 鸽巢排序
     * 限制过多，要求非负整数，且数字不宜过大
     */
    public static void PigeonholeSort(int[] data, boolean reverse, int max) throws SortException {
        PigeonholeSort(data, reverse, 0, data == null ? 0 : data.length - 1, max);
    }

    public static void PigeonholeSort(int[] data, boolean reverse, int left, int right, int max) throws SortException {
        check(data, left, right);
        int index = 0;
        int[] temp = new int[max + 1];
        for (int i = 0; i <= max; i++) {
            temp[i] = 0;
        }
        for (int i = left; i <= right; i++) {
            if (data[i] < 0 || data[i] > max) {
                throw new SortException(SortException.ERROR);
            } else {
                temp[data[i]]++;
            }
        }
        for (int i = 0; i <= max; i++) {
            for (int j = 0; j < temp[i]; j++) {
                data[left + index] = i;
                index++;
            }
        }
        reverse(data, reverse, left, right);
    }

    /**
     * 奇偶排序
     */
    public static void OddEvenSort(int[] data, boolean reverse) throws SortException {
        OddEvenSort(data, reverse, 0, data == null ? 0 : data.length - 1);
    }

    public static void OddEvenSort(int[] data, boolean reverse, int left, int right) throws SortException {
        check(data, left, right);
        boolean unsorted = true;
        while (unsorted) {
            unsorted = false;
            for (int i = left + 1; i <= right - 1; i += 2) {
                if (data[i] > data[i + 1]) {
                    swap(data, i, i + 1);
                    unsorted = true;
                }
            }
            for (int i = left; i <= right - 1; i += 2) {
                if (data[i] > data[i + 1]) {
                    swap(data, i, i + 1);
                    unsorted = true;
                }
            }
        }
        reverse(data, reverse, left, right);
    }

    /**
     * 臭皮匠排序
     */
    public static void StoogeSort(int[] data, boolean reverse) throws SortException {
        StoogeSort(data, reverse, 0, data == null ? 0 : data.length - 1);
    }

    public static void StoogeSort(int[] data, boolean reverse, int left, int right) throws SortException {
        check(data, left, right);
        stoogeSort(data, left, right);
        reverse(data, reverse, left, right);
    }

    private static void stoogeSort(int[] data, int left, int right) {
        if (data[left] > data[right]) {
            swap(data, left, right);
        }
        if ((right - left + 1) >= 3) {
            int split = (right - left + 1) / 3;
            stoogeSort(data, left, right - split);
            stoogeSort(data, left + split, right);
            stoogeSort(data, left, right - split);
        }
    }
}